package 所有的题类.E.位运算;


import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/**
 * 78. 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 *
 * 示例 2：
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 *
 * 提示：
 */
public class G子集78 {

    public static void main(String[] args) {
        int [] arr={1,2,3,4};
        int len=arr.length;
        List<List<Integer>> lists = subsetsEx(arr);

        lists.stream().forEach(x->{
            x.stream().forEach(c->{
                System.out.print(c+" ");
            });
            System.out.println();
        });
    }

    /**
     * 模范题解
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsetsEx(int[] nums) {
        int length = 1 << nums.length;
        List<List<Integer>> res = new ArrayList<>(length);
        //外层遍历子集的长度
        for (int i = 0; i < length; i++) {
            List<Integer> list = new ArrayList<>();
            //内层循环数组的长度,拿到每一位的二进制位的数字，比如7的二进制就是111》》对应的数据就是1,2,3
            for (int j = 0; j < nums.length; j++) {
                if (((i >> j) & 1) == 1)
                    list.add(nums[j]);
            }
            res.add(list);
        }
        return res;
    }

    public List<List<Integer>> subsets(int[] nums) {

        int len=nums.length;
        int c=1<<len;
        List<List<Integer>> all=new ArrayList<>();
        IntStream.rangeClosed(0, c-1).forEach(x->{
            String bin=Integer.toBinaryString(x);
            int remainLen=len-bin.length();
            StringBuffer sb=new StringBuffer();
            for (int i = 0; i < remainLen; i++) {
                sb.append("0");
            }
            sb.append(bin);
            List<Integer> list=new ArrayList<>();
            for (int i = 0; i < sb.length(); i++) {
                if(sb.charAt(i)=='1'){
                    list.add(nums[i]);
                }
            }
            all.add(list);
        });
        return all;
    }



}
